Swap Nodes in Pairs || Palindrome Partitioning II

发表于

Swap Nodes in Pairs

Question

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Analysis
  • 设置pre指针，指向每次颠倒前的前置指针，在两个变量交换位置后，需要将每对中的第二个变量的next更改为下一对的第二个
  • tmpnext标记为下一对待交换节点的第一个（起点）
  • 返回结果返回pre的下一个节点开始的链表
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null)
            return head;
        ListNode pre=new ListNode(1);
        pre.next=head;
        ListNode tmp1=head;
        ListNode result=pre;
        while(tmp1!=null&&tmp1.next!=null){
            ListNode tmp2=tmp1.next;
            ListNode tmpnext=tmp2.next;
            tmp1.next=tmp2.next;
            tmp2.next=tmp1;
            pre.next=tmp2;
            pre=tmp1;
            tmp1=tmpnext;
        }
        return result.next;
    }
}

Palindrome Partitioning II

Question

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Analysis

题目即找到一个字符串每个子串都是回文的最小划分数。

  • 采取Palindrome Partitioning题目的解法（循环+DFS）会超时
  • 利用动态规划，一个字符串为回文的条件有两种：1、 脚标为i+1到j-1的子串为回文且s[i]=s[j]. 2、s[i]==s[j] 且i、j相邻（j-i<2）
  • 设置dp变量 cuts[len+1]用以记录从脚标i到最后的字符串的最小划分数。当每次判断得s[i][j]为回文是，判断cut[i]与cut[j+1]+1的大小，并取其中较小者。cuts[i]表示从第i位置到第len位置（包含，即[i, len])的切割数（第len位置为空）。 初始时，是len-i。比如给的例子aab，cuts[0]=3，就是最坏情况每一个字符都得切割：a|a|b|’ ‘。cuts[1] = 2, 即从i=1位置开始，a|b|’ ‘。 cuts[2] = 1 b|’ ‘。cuts[3]=0,即第len位置，为空字符，不需要切割。
  • 当字符串[i,j]是回文后，说明从第i个位置到字符串第len位置的最小cut数可以被更新了， 那么就是从j+1位置开始到第len位置的最小cut数加上[i,j]|[j+1,len - 1]中间的这一cut。 即 Math.min(cuts[i], cuts[j+1]+1) 。最后返回cuts[0]-1。把多余加的那个对于第len位置的切割去掉，即为最终结果。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    public int minCut(String s) {
        int size=s.length();
        if(size==1||s==null)
            return 0;
        boolean[][] isPalindrome=new boolean[size][size];
        int[] cut=new int[size+1];
        char[] stmp=s.toCharArray();
        
        for (int i=0; i<=size; ++i){  
            cut[i] = size-i;  //cut nums from i to len [i,len]
        }  
        
        for(int i=size-1;i>=0;i--){
            for(int j=i;j<size;j++){
                if((stmp[i]==stmp[j]&&j-i<2)||(stmp[i]==stmp[j]&&isPalindrome[i+1][j-1]==true)){
                    isPalindrome[i][j]=true;
                    cut[i]=Math.min(cut[j+1]+1,cut[i]);
                }
            }
        }
        
        return cut[0]-1;
    }
}